题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：

• $0 <= n < 2^31$

注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

---

算法

(数位统计) $O(logn)$

首先我们知道的是，1 位数有 10 个，2 位数有 9 个，3 位数有 9 * 10 个，4 位数有 9 * 100 个

注意：从 1 开始计数；先不考虑 0，那么一位数就变成 9 个

三步操作

1. 确定是几位数，比如是三位数
2. 确定是几位数的第几个数，比如是三位数的第 20 个数，即 100 + 20 - 1 = 119。
3. 确定属于那个数的第几位

时间复杂度

总的时间复杂度即三步操作的时间复杂度

1. int 的范围 $2*10^9$，所以最多是 10 位数，因此第一步操作的时间是 $O(1)$ 的
2. 第二步除法向上取整，也是 $O(1)$ 的
3. 第三步求是第几位数字是 $O(log_{10}n)$ 的
   在二进制表示中取某一位可以每次右移 1 位（即除以 2），所以是 $O(log_2n)$ 级别的，
   同理在十进制中取某一位可以每次右移 1 位（即除以 10），所以是 $O(log_{10}n)$ 级别的

空间复杂度

$O(1)$

C++ 代码

class Solution {
public:
    int findNthDigit(int n) {
        // n ++ ; // 题目是从 0 开始计数，我们的思路是从 1 开始计数，相等于把 0 算到里面了，所以 n 往后移一位
        // n -- ; // 先不考虑 0，debug 之后发现 0 也满足不需要加特判

        // i 表示几位数，s 表示 i 位数有几个，base 表示第 i 位数的第一个数是谁
        long long i = 1, s = 9, base = 1;

        // 1. 确定是几位数
        while (n > i * s) {
            n -= i * s;
            i ++ ;
            s *= 10;
            base *= 10;
        }
        // 循环结束 n 存的就是第 i 位数的第几位

        // 2. 确定是 i 位数的第几个数：(n + i - 1) / i，需要向上取整，如果有余数说明是下一个数
        // number 存的就是这个数
        int number = base + (n + i - 1) / i - 1;
        // 求余数（第几位），如果 r = 0 表示是最后一位（也就是 i，几位数就是几），如果 r = 1 表示是第一位 ... 依此类推
        int r = n % i ? n % i : i;
        // 3. 取出这一位
        for (int j = 0; j < i - r; j ++ ) number /= 10;
        // 如果是 1 位数，个位就是答案，如果是多位数，经过第 3 步处理，个位也就是答案
        return number % 10;
    }
};